import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer,Employee> map = new HashMap<>();
        for (Employee e: employees){
            map.put(e.id,e);
        }
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(map.get(id));
        int ret = 0;
        while (!queue.isEmpty){
            Employee e = queue.poll();
            ret += e.importance;
            for (int subId: e.subordinates){
                queue.offer(map.get(subId));
            }
        }
        return ret;

    }
}

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] trustValues = new int [n + 1];
        for (int[] t: trust){
            trustValues[t[0]]--;
            trustValues[t[1]]++;
        }
        for (int i = 1; i <= n; i++){
            if (trustValues[i]  == (n - 1)){
                return i;
            }
        }
        return -1;
    }
}

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
                int sum = 0;
                for (int i: arr){
                    sum += i;
                }
                if(sum%3 != 0){
                    return false;
                }
                int left = 0;
                int leftSum = arr[left];
                int right = arr.length - 1;
                int rightSum = arr[right];
                while (left + 1 < right ){
                    if(leftSum == sum/3 && rightSum == sum/3){
                        return true;
                    }
                    if (leftSum != sum/3){
                        leftSum += arr[++left];
                    }
                    if (rightSum != sum/3){
                        rightSum += arr[--right];
                    }
                }
                return false;




            }
        }




    }
}

class Solution5 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char top = stack.peek();
                if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if (!stack.empty()){
            return false;

        }
        return true;




    }
}
public class Test0820 {
    public static void main(String[] args) {
    }
}
